#include <vector>
#include <stack>
#include <functional>
using namespace std;

void InsertSort(vector<int>& vc){
  for(size_t i = 0; i < vc.size()-1; ++i)
  {
    int end = i;
    int x = vc[end+1];
    while(end >= 0)
    {
      if(x < vc[end])
      {
        vc[end+1] = vc[end];
        --end;
      }
      else{
        break;
      }
      vc[end+1] = x;
    }
  }
}

void ShellSort(vector<int>& vc){
  int gap = vc.size();
  while(gap > 1)
  {
    gap = gap/3+1;
    for(size_t i = 0; i < vc.size()-gap; ++i)
    {
      int end = i;
      int x = vc[end+gap];
      while(end >= 0)
      {
        if(x < vc[end])
        {
          vc[end+gap] = vc[end];
          end-=gap;
        }
        else{
          break;
        }
        vc[end+gap] = x;
      }
    }
  }
}

void _insertSort(vector<int>& vc, int left, int right){
  for(int i = left; i < right-1; ++i)
  {
    int end = i;
    int x = vc[end+1];
    while(end >= left)
    {
      if(x < vc[end])
      {
        vc[end+1] = vc[end];
        --end;
      }
      else{
        break;
      }
      vc[end+1] = x;
    }
  }
}

void _quickSort(vector<int>& vc, int begin, int end);
int SegMent(vector<int>& vc, int begin, int end);

void QuickSort(vector<int>& vc){
  _quickSort(vc, 0, vc.size());
}

//void _quickSort(vector<int>& vc, int begin, int end){
//  if(end-begin<15)
//  {
//    _insertSort(vc,begin, end);
//    return;
//  }
//
//  int div = SegMent(vc, begin, end);
//  if(div-begin>1)
//  {
//    _quickSort(vc, begin, div);
//  }
//  if(end-(div+1)>1)
//  {
//    _quickSort(vc, div+1, end);
//  }
//}

void _quickSort(vector<int>& vc, int begin, int end){

  stack<int> st;
  st.push(begin);
  st.push(end);

  while(!st.empty())
  {
    end = st.top(); st.pop();
    begin = st.top(); st.pop();

    if(end-begin<15)
    {
      _insertSort(vc,begin, end);
      continue;
    }

    int div = SegMent(vc, begin, end);
    if(div-begin>1)
    {
      st.push(begin);
      st.push(div);
    }
    if(end-(div+1)>1)
    {
      st.push(div+1);
      st.push(end);
    }
  }
}

int GetMidIndex(vector<int>& vc, int left, int right){
  int midi = left+(right-left)/2;
  int tmp1 = vc[left]>vc[midi]? left:midi;
  int tmp2 = vc[right]>vc[midi]? right:midi;
  return vc[tmp1]>vc[tmp2]? tmp2:tmp1;
}


int SegMent(vector<int>& vc, int begin, int end){
  int midi = GetMidIndex(vc, begin, end-1);
  //if(midi != begin)
  //{
  //  swap(vc[midi], vc[begin]);
  //}
  swap(vc[midi], vc[begin]);
  int keyi = begin;
  int prev = begin;
  int cur = begin+1;
  while(cur < end)
  {
    if(vc[cur] < vc[keyi] && ++prev != cur)
    {
      swap(vc[prev], vc[cur]);
    }
    ++cur;
  }
  swap(vc[keyi], vc[prev]);
  return prev;
}

void _mergeSort(vector<int>& vc, vector<int>& tmp, int begin, int end);

void MergeSort(vector<int>& vc){
 vector<int> tmp;
 tmp.resize(vc.size());
 _mergeSort(vc, tmp, 0, vc.size());
}

//void MergeSort(vector<int>& vc){
// vector<int> tmp;
// tmp.resize(vc.size());
// size_t gap = 1;
// while(gap < vc.size())
// {
//   for(size_t begin = 0; begin<vc.size(); begin+=2*gap)
//   {
//      int begin1 = begin;
//      int end1 = begin1+gap;
//      int begin2 = begin+gap;
//      int end2 = begin2+gap;
//
//      int i = begin1;
//      if(end1 >= (int)vc.size())
//      {
//        end1 = vc.size();
//        while(end1-begin1>0)
//        {
//          tmp[i++] = vc[begin1++];
//        }
//        continue;
//      }
//
//      if(end2 > (int)vc.size())
//      {
//        end2 = vc.size();
//      }
//
//      while(end1-begin1>0 && end2-begin2>0)
//      {
//        if(vc[begin1] <= vc[begin2])
//        {
//          tmp[i++] = vc[begin1++];
//        }
//        else{
//          tmp[i++] = vc[begin2++];
//        }
//      }
//      while(end1-begin1>0)
//      {
//        tmp[i++] = vc[begin1++];
//      }
//      while(end2-begin2>0)
//      {
//        tmp[i++] = vc[begin2++];
//      }
//   }
//   for(size_t i = 0; i<vc.size(); ++i)
//   {
//      vc[i] = tmp[i];
//   }
//   gap*=2;
// }
//}

void _mergeSort(vector<int>& vc, vector<int>& tmp, int begin, int end){
  int midi = begin+(end-begin)/2;
  int begin1 = begin;
  int end1 = midi;
  int begin2 = midi;
  int end2 = end;
  if(end1-begin1>1){
    _mergeSort(vc, tmp, begin1, end1);
  }
  if(end2-begin2>1){
    _mergeSort(vc, tmp, begin2, end2);
  }
  int i = begin;
  while(end1-begin1>0 && end2-begin2>0)
  {
    if(vc[begin1] <= vc[begin2])
    {
      tmp[i++] = vc[begin1++];
    }
    else{
      tmp[i++] = vc[begin2++];
    }
  }
  while(end1-begin1>0)
  {
    tmp[i++] = vc[begin1++];
  }
  while(end2-begin2>0)
  {
    tmp[i++] = vc[begin2++];
  }
  for(int j=begin; j<end; ++j )
  {
    vc[j] = tmp[j];
  }
}

void AdjustDown(vector<int> &vc, int sz, int parent){
  int child = parent*2+1;
  while(child < sz){
    if(child+1 < sz && vc[child+1] > vc[child])
    {
      ++child;
    }
    if(vc[child] > vc[parent])
    {
      swap(vc[child], vc[parent]);
      parent = child;
      child = parent*2+1;
    }
    else{
      break;
    }
  }
}

void HeapSort(vector<int> &vc){
  for(int i = (vc.size()-2)/2; i>=0; --i)
  {
    AdjustDown(vc, vc.size(), i);
  }

  for(int end = vc.size()-1; end>0; --end)
  {
    swap(vc[0], vc[end]);
    AdjustDown(vc, end, 0);
  }
}
